Now that we understand why Postfix expressions are easy for stacks to evaluate, the next step is learning how to convert standard Infix expressions, like A + B * C, into that format using Edsger Dijkstra's Shunting-yard Algorithm.
The algorithm processes the input expression token-by-token, separating operands from operators and managing their required order using two primary structures, both relying on the underlying FILO principle:
- Output List (Queue): This structure receives operands immediately and operators only when their precedence rules allow. This list accumulates the final Postfix result.
- Operator Stack: This stack is the critical component that manages operator precedence.
When an operator is encountered in the input, it must be compared against the operator currently at the top of the Operator Stack. This comparison dictates whether the stack's existing operators must be popped out first or whether the new operator can be pushed.
Token Actions
| Token Type | Action on Operator Stack | Action on Output List |
|---|---|---|
| Operand (e.g., A, 10) | Ignore | Append immediately. |
| Operator (e.g., +, *) | Pop higher/equal precedence ops, then PUSH self. | Receive popped operators. |